package com.hqq.exercise.array;

/**
 * InversePairs 数组中的逆序对
 * 题目描述:
 * 在数组中的两个数字如果前一个数字大于后一个数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组的逆序对的总数
 * 样例输入:
 * {7,5,6,4}
 * 样例输出:
 * 5
 * //（7,6）、（7、5），（7、4），（6、4），（5、4）
 * 思路:
 * 先把数组不断进行对半拆分到单个元素 统计每组的逆序对数
 * 之后将每组进行合并 并统计逆序数
 * [用两个指针指向两个子数组的末尾，每次比较指针指向的元素,如果第一个子数组的数字大于第二个子数组中的数字,
 * 构成逆序对,并且逆序数等于第二个子数组剩余数字个数,小于则不构成。每个把较大的数字复制到辅助数组,往前移动指针继续比较]
 * Created by heqianqian on 2017/8/21.
 */
public class InversePairs {

    public static int countInversePairs(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        //最基本的做法 TAT
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[i]) {
                    count++;
                }
            }
        }
        return count;
    }

    public static int countInversePairsOptimized(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int[] copy = array.clone();
        return mergeSort(array, copy, 0, array.length - 1);
    }

    private static int mergeSort(int[] array, int[] result, int start, int end) {
        if (start == end) {
            result[start] = array[start];
            return 0;
        }
        int length = (end - start) / 2;
        int left = mergeSort(result, result, start, start + length);
        int right = mergeSort(result, result, start + length + 1, end);
        int leftIndex = start + length;
        int rightIndex = end;
        int count = 0;
        int point = rightIndex;
        while (leftIndex >= start && rightIndex >= start + length + 1) {
            if (array[leftIndex] > array[rightIndex]) {
                result[point--] = array[leftIndex--];
                count += rightIndex - start - length;
            } else {
                result[point--] = array[rightIndex--];
            }
        }
        for (int i = leftIndex; i >= start; i--) {
            result[point--] = array[i];
        }
        for (int j = rightIndex; j >= start + length + 1; j--) {
            result[point--] = array[j];
        }
        return left + right + count;
    }
}
